import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;

/**
 * 排序算法：升序
 */
public class SortingAlgorithm {
    // 0.交换函数
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    // 1.直接插入排序 O(n^2)
    private static void insertSort(int[] arr) {
        // 从第二个元素开始向前比较，如果当前元素比前面元素小，
        // 向前挪动，直到找到插入位置
        // 外层循环表示待插入元素，内层循环表示找位置
        for (int i = 1; i < arr.length; i++) {
            // 先记录一下当前元素
            int index = 0;
            int val = arr[i];
            for (int j = i - 1; j >= 0; j--) {
                if (val < arr[j]) {
                    // 向前挪动腾位置
                    arr[j + 1] = arr[j];
                } else {
                    // 找到位置
                    index = j + 1;
                    break;
                }
            }
            // 插入
            arr[index] = val;
        }
    }

    // 2.希尔排序 O(n^1.3~n^1.5)
    private static void shellSort(int[] arr) {
        // 先确定分组，第一次分组为 arr.length/2，逐渐分解，直到 gap == 1
        // 每个分组内插入排序即可
        int gap = arr.length / 2;
        while (gap != 1) {
            shell(arr, gap);
            gap /= 2;
        }
        shell(arr, 1);
    }

    private static void shell(int[] arr, int gap) {
        // i = gap 刚好可以执向当前分组的第二个元素
        for (int i = gap; i < arr.length; i++) {
            int val = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arr[j + gap] < arr[j]) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            // 替换
            arr[j + gap] = val;
        }
    }

    // 3.直接选择排序 O(n^2)
    private static void selectSort(int[] arr) {
        // 每次找到未排序数组中最小的元素，放到已排序列的最后一个位置即可
        // 外层循环表示已排序序列，内层循环，表示未排序序列
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 此时 minIndex 表示最小下标
            swap(arr, minIndex, i);
        }
    }

    // 4.堆排序 O(Nlog(N))
    private static void heapSort(int[] arr) {
        // 1.建堆
        createHeap(arr);
        // 2.堆排序: 循环将堆顶元素替换到堆尾,每交换一次确定一个有序位置
        int times = arr.length - 1;
        while (times > 0) {
            swap(arr, 0, times);
            //  向下调整
            shiftDown(arr, 0, times);
            times--;
        }
    }

    // 建堆（向下调整建堆 O(N)）
    private static void createHeap(int[] arr) {
        // 从最后一个非叶子结点开始向下调整建堆 2x + 1 = n, 2x + 2 = n --> x = n-1/2  n-2/2
        // 最后一个叶子结点的父节点下标：index = ((arr.length - 1) - 1) / 2
        int parentIndex = (arr.length - 2) / 2;
        while (parentIndex >= 0) {
            // 向下调整
            shiftDown(arr, parentIndex, arr.length);
            parentIndex--;
        }
    }

    // 向下调整算法,由于此时是排升序，所以建大根堆 O(logN)
    private static void shiftDown(int[] arr, int parentIndex, int len) {
        // 孩子结点
        int child = 2 * parentIndex + 1;
        while (child < len) {
            // 找到最大的孩子下标
            if (child + 1 < len && arr[child + 1] > arr[child]) child = child + 1;
            if (arr[parentIndex] < arr[child]) {
                // 交换
                swap(arr, parentIndex, child);
                // 修改下标，继续向下调整
                parentIndex = child;
                child = 2 * parentIndex + 1;
            } else {
                // 无需交换，那么下面也不必再比较了
                break;
            }
        }
    }


    // 5.冒泡排序 O(n^2)
    private static void bubbleSort(int[] arr) {
        // 比较相邻元素，每次将最大的元素放到末尾
        // 外层循环表示比较的轮次(5 个数比较 4 轮)
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层循环控制每轮比较次数
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            if (!flag) {
                // 说明某一轮没有比较，此时直接跳出即可，因为已经有序
                break;
            }
        }
    }

    // 6.快速排序 O(nlog(n))
    private static void quickSort(int[] arr) {
        // 快速排序使用的是一种分治排序，类似于二叉树的交换方式。
        // 每次确定一个基准值，每次就会根据这个基准值，将排序序列分割成两个子序列
        // 左子序列中的值，小于基准值，右边大于基准值
        // 左右子序列都重复上面的过程，直到最终有序
        quick(arr, 0, arr.length - 1);


    }

    private static void quick(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
//        int pivotIndex = partition(arr,start,end);
        int pivotIndex = partition2(arr, start, end);
        quick(arr, start, pivotIndex);
        quick(arr, pivotIndex + 1, end);
    }

    // 分割并确定基准值位置 Hoare
    private static int partition(int[] arr, int start, int end) {
        int left = arr[start];
        int i = start;
        while (start < end) {
            while (start < end && arr[end] >= left) {
                end--;
            }
            while (start < end && arr[start] <= left) {
                start++;
            }
            swap(arr, start, end);
        }
        swap(arr, i, start);
        return start;
    }

    // 分割并确定基准值位置 挖坑法
    private static int partition2(int[] arr, int start, int end) {
        int pivot = arr[start];
        while (start < end) {
            while (start < end && arr[end] >= pivot) {
                end--;
            }
            // 入坑
            arr[start] = arr[end];
            while (start < end && arr[start] <= pivot) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = pivot;
        return start;
    }

    // 7.归并排序 O(Nlog(N))
    private static void mergeSort(int[] arr) {
        // 归并排序是一种分治思想，先“归”，在“并”的过程中，先让子序列有序，逐渐让整个序列有序
        merge(arr, 0, arr.length - 1);
    }

    private static void merge(int[] arr, int start, int end) {
        // 递归终止条件
        if (start >= end) return;
        // 先递归分解为子序列
        int mid = (start + end) / 2;
        merge(arr, start, mid);
        merge(arr, mid + 1, end);
        // 合并
        combine(arr,start,mid,end);
    }

    private static void combine(int[] arr, int start, int mid, int end) {
        int len = end - start + 1;
        // 创建临时数组
        int[] tmp = new int[len];
        // 排序这两个有序子序列
        int i = start;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j]) {
                tmp[index ++] = arr[i ++];
            } else {
                tmp[index ++] = arr[j ++];
            }
        }
        // 处理剩余元素
        while (i <= mid) {
            tmp[index ++] = arr[i ++];
        }
        while (j <= end) {
            tmp[index ++] = arr[j ++];
        }
        // 修改原数组数据
        for (int k = 0; k < len; k ++) {
            arr[k + start] = tmp[k]; // 上面用的是 for 循环，这里就不要再 ++ 了！！！
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 4, 2, 1, 9, 0, 3, 8, 5, 7};
//        insertSort(arr);
//        shellSort(arr);
//        selectSort(arr);
//        bubbleSort(arr);
//        quickSort(arr);
//        quick1(arr, 0, arr.length - 1);
//        heapSort(arr);
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    // 8.计数排序


//    // 快速排序复写
//    private static void quick1(int[] arr, int start, int end) {
//        // 递归终止条件
//        if (start >= end) return;
//
////        int pivotIndex = partition11(arr, start, end);
//        int pivotIndex = partition22(arr,start,arr.length-1);
//        // 排左边
//        quick1(arr, start, pivotIndex);
//        // 排右边
//        quick1(arr, pivotIndex + 1, end);
//    }
//
//    // hoare
//    private static int partition11(int[] arr, int start, int end) {
//        int pivot = arr[start];
//        int index = start;
//        while (start < end) {
//            // 右边找到一个比基准值小的数
//            while (start < end && arr[end] >= pivot) end--;
//            // 左边找到一个比基准值大的数
//            while (start < end && arr[start] <= pivot) start++;
//            // 找到后交换
//            swap(arr, start, end);
//        }
//        // 最后基准值位置交换
//        swap(arr, start, index);
//        return start;
//    }
//
//    // 挖坑法
//    private static int partition22(int[] arr, int start, int end) {
//        // 初始时当前位置作为坑位
//        int pivot = arr[start];
//
//        while (start < end) {
//            // 右边找到一个比基准值大小的
//            while (start < end && arr[end] >= pivot) end--;
//            arr[start] = arr[end];
//            // 左边找到一个比基准值大的
//            while (start < end && arr[start] <= pivot) start++;
//            arr[end] = arr[start];
//        }
//        // 最后剩一个坑位填充基准值
//        arr[start] = pivot;
//        return start;
//    }
}
